{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Traversing 2 trees in parallel（并行遍历2棵树）][1]\n",
    "\n",
    "[1]: https://mp.weixin.qq.com/s/9jcifxrVKeQ7iXl8V9s4yw\n",
    "\n",
    "![Logo](images/PT-1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "****\n",
    "\n",
    "**For English accounts only: This time, the original article is in English. Please go to the link attached in the title of this *Jupyter Notebook*. Thank you!**\n",
    "\n",
    "****"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;这道题目频繁地出现，所以我打算分享它。我在众多的“脸谷面试”中遇到了这个问题。\n",
    "\n",
    "- 给定2棵树，判断它们是否为一组拷贝？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;题目模糊吗？是的，它是故意这么含糊的。有时，面试官会故意挖坑，看看您是否可以定义问题范围并提出必要的澄清问题。数据结构是什么？功能标注是什么？ 有类定义吗？这棵树长什么样？有几个子节点？这一切都取决于你。你将如何设计？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;如果你想要解决它，那就试试看吧！我特别鼓励你这么做。当你已经准备好查看解决方案时，那就继续往下读。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;因此，这道题关于并行遍历两棵树。这个问题许多变种，例如：\n",
    "\n",
    "- 两棵树分别是对方的拷贝吗？\n",
    "- 在一棵树中，是否存在一个节点被认定与另一棵树中的一个节点相同？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;现实是，许多编程专业的学生都学了“如何遍历一棵树”……所以他们认为他们都知道该怎么做。但是当被要求同时遍历两棵树时，有时会使人们陷入困境并真正测试他们是否理解算法……或者他们是否只是反省了他们在其他地方看到的答案。这也不是一件容易的事，这就是使这个问题如此受欢迎的原因。你应该知道的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;另一个有趣的事情是，我将使用2种变体对此进行编程。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;首先，我建议您考虑如何表示子节点。有时，将它们表示为数组比将其表示为“左节点”和“右节点”更为简单。有时，一棵树可以具有多个分支，因此数组表示更加灵活。这取决于眼前的问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;我想在这里向您展示的第二件事是递归和迭代形式的实现。仔细研究这些内容，您会发现递归形式要简单得多。迭代形式需要传递很多状态，几乎可以保证创建一个新的数据结构来封装两个节点的状态。为了简洁起见，我使用“数组堆栈”解决了这个问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;还有一点——我正在使用面向对象的样式。即我将使用`a.isClone(b)`的形式取代`isClone(a，b)`的形式。很多人不会这样做，但这并不影响。请注意，有多种方法可以执行这些方法参数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;欢迎各位批评指正！"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    ''' Node Structure Definition'''\n",
    "    \n",
    "    def __init__(self, value=None, children=[]):\n",
    "        ''' The Constructor '''\n",
    "        self.value = value\n",
    "        self.children = children\n",
    "\n",
    "    def __str__(self):\n",
    "        ''' Tree output prettify by pre-order traversal '''\n",
    "        string = str(self.value)\n",
    "        for child in self.children:\n",
    "            string += str(child)\n",
    "        return string\n",
    "\n",
    "    def isClone_recursivly(self, node_B):\n",
    "        ''' Check if a subtree is a clone of another tree: Recursive Algorithm '''\n",
    "        if self.value != node_B.value:\n",
    "            return False\n",
    "        if len(self.children) != len(node_B.children):\n",
    "            return False\n",
    "        for index in range(len(self.children)):\n",
    "            if not self.children[index].isClone_recursivly(node_B.children[index]):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def isClone_iterativly(self, node_B):\n",
    "        ''' Check if a subtree is a clone of another tree: Iterative Algorithm '''\n",
    "        stack = [(self, node_B)]\n",
    "        while len(stack) > 0:\n",
    "            (temp_A, temp_B) = stack.pop()\n",
    "            if temp_A.value != temp_B.value:\n",
    "                return False\n",
    "            if len(temp_A.children) != len(temp_B.children):\n",
    "                return False\n",
    "            for index in range(len(temp_A.children)):\n",
    "                stack.append((temp_A.children[index], temp_B.children[index]))\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''\n",
    "Test Cases:\n",
    "\n",
    "        1\n",
    "       / \\\n",
    "      2   3\n",
    "     / \\\n",
    "    4   5\n",
    "'''\n",
    "tree_A = Node(1, [\n",
    "    Node(2, [\n",
    "        Node(4),\n",
    "        Node(5)\n",
    "    ]),\n",
    "    Node(3)\n",
    "])\n",
    "tree_B = Node(1, [\n",
    "    Node(2, [\n",
    "        Node(4),\n",
    "        Node(5)\n",
    "    ]),\n",
    "    Node(3)\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree_A.isClone_recursivly(tree_B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree_A.isClone_iterativly(tree_B)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
